# 高塔(不懂)
"""回溯(DFS)算法可以转换为DP算法的条件
1. 重叠子问题 (Overlapping Subproblems)
    回溯过程中存在大量重复计算的子问题，不同递归路径会多次计算相同状态。 例如：斐波那契数列递归树中，计算 fib(5) 时多次重复计算 fib(3)。
2. 最优子结构 (Optimal Substructure)
    问题的最优解可以由其子问题的最优解推导而来。 例如：最短路径问题中，A→B→C 的最短路径 = A→B 的最短路径 + B→C 的最短路径。
3. 状态可被唯一表示
    所有递归状态可以用有限的参数（如位置、剩余资源等）唯一描述，且参数范围合理。
4. 状态转移可被显式定义
    子问题之间的关系可以写出明确的递推公式（状态转移方程）。
"""


def combination(m, k):
    """计算组合数C(m, k)，从m中选取k个的不同的组合个数."""
    if k < 0 or k > m:
        return 0

    if k == 0 or k == m:
        return 1
    k = min(k, m - k)
    result = 1
    for i in range(1, k + 1):
        result = result * (m - k + i) // i
    return result


def tower(arr, m):
    """应该也是一种正确的解法, 但是可能数字太大计算模的时候会错误"""
    MOD = 998244353
    n = len(arr)
    # dp[r][e] 表示从回合 r 开始，剩余能量为 e 的过程数
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 游戏最多进行 n 回合后结束，无论能量剩多少都视为一种过程
    for e in range(m + 1):
        dp[n][e] = 1

    # 从后往前计算回合 r = n-1 到 0
    for r in range(n - 1, -1, -1):
        for e in range(1, m + 1):  # e 必须正数，否则游戏已经结束
            total = 0
            # 枚举本回合消耗的能量 c
            for c in range(1, e + 1):
                ways = (arr[r] * c) % MOD  # 本回合不同表现的结果数
                if e - c == 0:
                    # 消耗后能量耗尽，本回合结束游戏
                    total = (total + ways) % MOD
                else:
                    # 消耗后还有能量，后续回合的方案乘上本回合结果数
                    total = (total + ways * dp[r + 1][e - c] % MOD) % MOD
            dp[r][e] = total
    return dp[0][m]


def tower_std(arr, m):
    mod = 998244353  # 使用局部变量而非全局变量
    n = len(arr)

    def power_mod(x, b, mod):
        """快速幂算法：计算 (x^b) % mod"""
        return pow(x, b, mod)

    def C(u, v, mod):
        """计算组合数 C(u, v) % mod"""
        ans = 1
        # 计算阶乘部分
        for i in range(u, u - v, -1):
            ans = ans * i % mod
        # 计算阶乘的逆元部分
        for i in range(1, v + 1):
            ans = ans * power_mod(i, mod - 2, mod) % mod
        return ans

    def Lucas(n, m, mod):
        """Lucas 定理计算组合数 C(n, m) % mod"""
        if m == 0:
            return 1
        return (C(n % mod, m % mod, mod) * Lucas(n // mod, m // mod, mod)) % mod

    # 初始化 ma 数组
    ma = [1] * (n + 1)
    for i in range(1, n + 1):
        ma[i] = ma[i - 1] * arr[i - 1] % mod

    # 计算 ans
    ans = 0
    tmp = m % mod
    qq = (m % mod) * (m % mod) % mod

    for i in range(1, n):
        ans = (ans + ma[i] * tmp) % mod
        tmp = tmp * ((qq + mod * 50 - i * i) % mod) % mod
        tmp = tmp * power_mod(4 * i * i + 2 * i, mod - 2, mod) % mod

    ans = (ans + Lucas(m + n, 2 * n, mod) * ma[n] % mod) % mod
    return ans


if __name__ == '__main__':
    arr = [3, 2, 5, 7, 1, 4, 6, 8, 3]
    m = 15
    print(tower(arr, m))
    print(tower_std(arr, m))
    arr = [1, 2, 1]
    m = 3
    print(tower(arr, m))
    print(tower_std(arr, m))
